#include "junix.h"
using namespace std;

template <typename Iterator>
void jinplace_merge(Iterator& p, Iterator& q, Iterator& r) {
	typedef iterator_traits<Iterator>::value_type value_type;
	typedef vector<value_type> VEC;
	VEC V(p,r);
	VEC::iterator p2=V.begin(),q2=p2+(q-p),r2=V.end();
	while (p2<q2 && q2<r2) {
		if (*p2<*q2) {
			*p++ = *p2++;
		} else {
			*p++ = *q2++;
		}
	}

	if (p2<q2)
		copy(p2,V.begin()+(q-p),p);
	else 
		copy(q2,V.end(),p);
}	


int main(int argc, char **argv)
{
	int v[] = {1,9,2,8,3,7,8,2,1,5};
	sort(v,v+5);
	sort(v+5,v+10);

	copy(v,v+10,ostream_iterator<int>(cout," "));
	cout<<"\n";
	//inplace_merge(v,v+5,v+10);
	jinplace_merge(v,v+5,v+10);
	copy(v,v+10,ostream_iterator<int>(cout," "));
	cout<<"\n";
}
